#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-11-11 11:12 上午
# @Author  : yangdy
# @File    : 2020-11-11.514.自由之路
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        # memo = {}
        #
        # def dfs(i, j):
        #     nonlocal ring, key
        #     if (i, j) in memo:
        #         return memo[(i, j)]
        #
        #     if j == len(key):
        #         return 0
        #
        #     left = float('inf')
        #     for k in range(len(ring)):
        #         idx = (i + k) % len(ring)
        #         if ring[idx] == key[j]:
        #             left = dfs(idx, j + 1) + k
        #             break
        #
        #     right = float('inf')
        #     for k in range(len(ring)):
        #         idx = (i - k + len(ring)) % len(ring)
        #
        #         if ring[idx] == key[j]:
        #             right = dfs(idx, j + 1) + k
        #             break
        #
        #     memo[(i, j)] = min(left, right)
        #     return memo[(i, j)]
        #
        # return dfs(0, 0) + len(key)
        dp = [[-1 for j in range(len(ring))] for i in range(len(str) + 1)]
        mm = {}
        for i in range(len(ring)):
            if not mm.get(ring[i]):
                mm[ring[i]] = [i]
            else:
                mm[ring[i]].append(i)





